package com.aha.seventhchapter.fourth;

import java.util.Scanner;

/**
 * Created by wangxin on 2015/10/25.
 * 并查集
 */
public class DisjointSets {
    int[] f = new int[1000];
    int n,m,sum=0;
    private void init(int n,int m){
        this.n = n;
        this.m = m;
        for (int i = 0; i < n; i++) {
            f[i] = i;
        }
    }

    /**
     * 找爹的递归函数，不停的找直到找到祖宗为止。这里用于找最高犯罪团伙的领导人，擒贼先擒王原则
     * @param v
     * @return
     */
    private int getParent(int v){
        if(f[v] == v){
            return v;
        }else{
            //这里是路径压缩，每次在函数返回的时候顺带把路上遇到的人的BOSS改为最后找到的祖宗编号，也就是犯罪团伙的最高领导人编号。这样可以提高今后找到犯罪团伙的最高领导人（其实就是输的祖先）的速度
            f[v] = getParent(f[v]);
            return f[v];
        }
    }

    /**
     * 这里是合并两个自己和的函数
     * @param v
     * @param u
     */
    private void merge(int v, int u){
        int t1,t2;
        t1 = getParent(v);
        t2 = getParent(u);
        if(t1 != t2){
            f[t2] = t1;
            //"靠左"原则，左边变成右边的BOSS，即把右边的集合作为左边集合的子集合。
            //经过路径压缩以后，将f[u]的根的值也赋值为v的祖先f[t1]
        }
    }

    public static void main(String[] args) {
        int x,y;
        DisjointSets ds = new DisjointSets();
        Scanner scan = new Scanner(System.in);
        System.out.println("input n:");
        int n = scan.nextInt();
        System.out.println("input m:");
        int m = scan.nextInt();
        ds.init(n, m);
        for (int i = 0; i < m; i++) {
            //开始合并犯罪团伙
            System.out.println("input x:");
            x = scan.nextInt();
            System.out.println("input y:");
            y = scan.nextInt();
            ds.merge(x,y);
        }
        //最后扫描有多少个独立的犯罪团伙
        for (int i = 0; i < n; i++) {
            if(ds.f[i] == i){
                ds.sum++;
            }
        }
        System.out.println("共有" + ds.sum + "个犯罪团伙！");
    }
}
